package Leetcode;

/**
 * @Author piper
 * @Date 2019/10/22 2:50 下午
 */
public class 力扣66_加一 {

    /**
     * 照着要求写的算法
     * 第一步 将最后一位加一
     * 第二步 有进位往前叠加
     * 第三步 循环后还有进位 数组加一
     */
    static int[] plusOne(int[] digits) {
        int j = 0;
        int c = 0;

        //1 最后一位加1
        c = digits[digits.length - 1] + 1;
        j = c / 10;
        digits[digits.length - 1] = c % 10;

        //2 如果有进位 往前叠加
        for (int k = digits.length - 2; k >= 0 && j > 0; k--) {
            c = digits[k] + j;
            j = c / 10;
            digits[k] = c % 10;
        }

        //3 如果数组满了 还有进位 增加数组长度
        if (j > 0) {
            int[] newdig = new int[digits.length + 1];
            newdig[0] = j;
            System.arraycopy(digits, 0, newdig, 1, digits.length);
            digits = newdig;
        }

        return digits;
    }

    /**
     * 其他人的解法
     * 主要是抓住了题目的特点
     * 除了9之外 其他数字加1不会有进位
     * 9+1的进位只能是1 并且原来位置只能是0
     * 发现本位为0就退出循环
     * 如果循环完毕了没有退出 说明遇到了999...这种情况
     * 直接创建一个比原来长一的数组 第一位设置为1
     */
    static int[] plusOne1(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) return digits;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }

    public static void main(String[] args) {
        int[] l = plusOne1(new int[]{9, 9, 9, 9});
        for (int i = 0; i < l.length; i++) {
            System.out.print(l[i] + "\t");
        }
    }
}
